package com.mid;

/**
 * Created by Lxk on 2019/6/3.
 */
public class Solution147 {

    /**
     *
     * @param head
     * @return
     */
    public ListNode insertionSortList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode help = new ListNode(0);
        help.next = head;
        ListNode cur = head.next;
        head.next = null;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = null;
            ListNode findFirstBigger = help.next;
            ListNode findPre = help;
            while(findFirstBigger!=null&&findFirstBigger.val<cur.val){
                findFirstBigger = findFirstBigger.next;
                findPre = findPre.next;
            }
            cur.next = findPre.next;
            findPre.next = cur;
            cur = next;
        }
        return help.next;
    }







    public static void main(String[] args) {
        ListNode node = new ListNode(3);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(2);
        node.next = node2;
        node2.next = node3;
        node3.next = node4;
        Solution147 solution147 = new Solution147();
        ListNode head = solution147.insertionSortList(node);
        ListNode cur = head;
        while(cur!=null){
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

}
